Directories are employed for accessing data in computerized data bases. A common form of directory is the so-called "tree" directory wherein an upper directory level points to a lower directory level which, in turn, points to possibly lower directory levels which, in turn, identify the location of data which can be accessed. The highest level of the directory is often called the "root directory". An example of such a directory structure is used in disk operating systems (DOS) of the IBM Personal Computer Computer Language Series identified by Manual Part Number 1502343, Copyright 1983, International Business Machines Corporation, Armonk, N.Y. The directory structure can be viewed in DOS by either a TREE command or a directory command DIR. The DOS command PATH which can be used as a SET SEARCH directory command indentifies a path to the various directory levels to access a single file or group of files. In DOS, each file is referred to by a filename with an optional extension of three alphabetic characters. The filename and extension are separated by a period. Another example of a tree directory is shown in Wang, U.S. Pat. No. 4,468,728.
In DOS Version 2.1, as used on the IBM Personal Computer XT machine, the root directory is stored in an outer track of a so-called hard disk (magnetic storage), whereas the various lower levels called "subdirectories" are dispersed throughout the data storage disk. The system works fine for magnetic data storage disks which are rewritable and in which the capacity of the disk are relatively modest, i.e., less than 50 megabytes of storage. Therefore, it is desired to have an improved tree type of directory usable with DOS and other operating systems for efficiently managing data stored on a large capacity disk, i.e., 200 megabytes and more. Such management should be conducted without extensive requirements for large compute power. Some optical disks are so-called "write once disks"; that is, recording on the disk surface results in a nonreversible recording such as by ablation, change between amorphous an crystalline material states, changing the topography of the disk without ablation, changing color of the disk, and the like. Write once is also termed "indelible recording". In a data processing environment, as opposed to a video or image-capturing environment, the data to be stored on the disk as updates to files do not, in general, occur in a linear fashion. This means the size of the directory needed for describing the data to be stored cannot be predetermined; that is, a directory management technique is required which will make the best use of the data storage space while minimizing directory search time for locating allocated data storage locations on the disk (also termed data storage space). In other words, the information available in each directory block should be maximized while minimizing consumption of data storage space and directory search times for accessing such allocated space. Each directory should have its allocated data storage space filled to the utmost which simultaneously conserves data storage space while reducing search time.
While the principles and philosophies set forth above are of particular interest to indelibly-recorded data, the principles involved are also applicable to rewritable, or reversible, data storage.
In either type of storage, the addition of data to be stored in the nonlinear manner means that the directory will increase in size. Accordingly, the directory structure should be completely modular and self-contained insofar as it is constructed while permitting extensive changes and extensions. In another aspect, which is of particular interest to indelible recording, an optical data storage disk, for example, may be prepared with a read-only segment. Such read-only segment may employ the same type of recording as used in the to be received indelible recording. When the optical disk is shipped from a factory, the read-only portion, of course, is recorded on the disk; it will have a corresponding modular directory for that read-only data. When a user receives the disk, the user can add additional data and modularly expand the directory such that when the disk has been filled with data, there is a single directory for all of the data and stored on the disk. The directory should also be changeable to accommodate defragmentation of data on the indelible recording. This action is achieved by adding additional modules to the data that are recorded, as well as to the directory.
Search time in any directory can be critical to the success of a data storage device as well as the rapid access to a data base. Such searching has been facilitated through the use of indexing the data base or the directory structure. An example of indexing is shown in U.S. Pat. No. 4,611,272. To identify or locate data, only the index need be searched; this fact means that fewer data entries need be examined for finding the data, hence reducing the search time. In some data bases, one of the fields in each entry is designated as the index field. Usually, such index field is selected to be the first-entered field, i.e., the first field occurring at the beginning of each entry area and which would always be the first field accessed. The informational contents of such fields can be extracted from the data base and set up in a separate data base index with the data base index being searched independently of the data entries. A limitation to such a system is to ensure the proper selection of which field to use as an index. Other data bases permit any one of the fields to be used as an index field with that field being extracted into a separate file. Of course, in both situations, additional data storate space is required for storing the separate index file. Tree-type data directories have been indexed in a similar manner. An improved indexing scheme is desired, particularly for accommodating an expandable modular directory for handling multiple versions of data in a relatively simple manner while minimizing costly software overhead.
In write-once, or indelible, recording technologies it is desired to completely fill as much of the disk sectors, or data storage areas, as possible. Accordingly, it is further desired to provide an expandable modular directory which tends to maximize utilization of data storate space while keeping the directory relatively compact for rapid index searching.